﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0078_PermuteUnique : IAlgorithm
    {
        // 47. 全排列 II

        // 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

        // 提示：
        //  1 <= nums.length <= 8
        //  -10 <= nums[i] <= 10

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 3, 3, 0, 3 };
            // 算法执行与打印
            var res = PermuteUnique(nums);
            foreach (var item in res)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public IList<IList<int>> PermuteUnique(int[] nums)
        {
            var res = new List<IList<int>>();
            var nusmList = nums.ToList();
            nusmList.Sort();
            Backtrack(nusmList, 0, new bool[nums.Length], new List<int>(), res);
            return res;
        }
        private void Backtrack(List<int> nums, int i, bool[] vis, List<int> temp, List<IList<int>> res)
        {
            if (i == nums.Count)
                res.Add(temp.ToArray());
            else
                for (int j = 0; j < nums.Count; j++)
                {
                    if (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1] || vis[j])
                        continue;
                    temp.Add(nums[j]);
                    vis[j] = true;
                    Backtrack(nums, i + 1, vis, temp, res);
                    temp.RemoveAt(temp.Count - 1);
                    vis[j] = false;
                }
        }

    }
}
